#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""



class Solution:
    def minCut(self, s):
        self.s = s
        self.l = len(s)
        self.records = self.make_matrix(self.l, self.l, 0)      # mat[i][i] == 0, 对角线都为0, 因为单个字符都是回文

        # span = [right - left], left和right都是闭区间(对角线的span为0)
        for span in range(1, self.l):
            for begin in range(0, self.l - span):
                left = begin
                right = begin + span
                self.records[left][right] = self.calc(left, right)

        return self.records[0][-1]

    def calc(self, left, right):
        # [left, right] : 闭区间

        if self.s[left] == self.s[right] and self.records[left+1][right-1] == 0:
            # 如果[left, right]组成了回文串, 返回0
            return 0

        local_min = self.l

        for split in range(left, right):
            sum_cut = self.records[left][split] + self.records[split+1][right] + 1
            local_min = min(sum_cut, local_min)
            if local_min == 1:
                return 1

        return local_min

    def make_matrix(self, rows, cols, init_value=None):
        one_row = [init_value] * cols
        return [list(one_row) for i in range(rows)]


def main():
    print("start main")
    s = Solution()
    # ret = s.minCut('aabccbaa')
    input= "apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp"
    # ret = s.minCut('abcdefg')
    ret = s.minCut(input)
    print(ret)

if __name__ == "__main__":
    main()
